package Year22_Month06.day25;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class 组合总和 {

    List<List<Integer>> list = new ArrayList<>();//最终的元素集合
    LinkedList<Integer> path = new LinkedList<>();

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        backtracking(candidates,0,target,0);
        return list;
    }

    public void backtracking(int[] nums,int startIndex,int target,int sum){
        if(sum == target){
            list.add(new LinkedList<>(path));
        }
        for (int i = startIndex; i < nums.length; i++) {
            if(sum + nums[i] > target) break;
            path.add(nums[i]);
            backtracking(nums, i, target, sum + nums[i]);
            path.removeLast();
        }
    }
}
